

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<html>


<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">

<base target="_top">
<style type="text/css">
  

/* default css */

table {
  font-size: 1em;
  line-height: inherit;
  border-collapse: collapse;
}


tr {
  
  text-align: left;
  
}


div, address, ol, ul, li, option, select {
  margin-top: 0px;
  margin-bottom: 0px;
}

p {
  margin: 0px;
}


pre {
  font-family: Courier New;
  white-space: pre-wrap;
  margin:0;
}

body {
  margin: 6px;
  padding: 0px;
  font-family: Verdana, sans-serif;
  font-size: 10pt;
  background-color: #ffffff;
  color: #000;
}


img {
  -moz-force-broken-image-icon: 1;
}

@media screen {
  html.pageview {
    background-color: #f3f3f3 !important;
    overflow-x: hidden;
    overflow-y: scroll;
  }

  

  body {
    min-height: 1100px;
    
    counter-reset: __goog_page__;
  }
  
  * html body {
    height: 1100px;
  }
  /* Prevent repaint errors when scrolling in Safari. This "Star-7" css hack
     targets Safari 3.1, but not WebKit nightlies and presumably Safari 4.
     That's OK because this bug is fixed in WebKit nightlies/Safari 4 :-). */
  html*#wys_frame::before {
    content: '\A0';
    position: fixed;
    overflow: hidden;
    width: 0;
    height: 0;
    top: 0;
    left: 0;
  }
  
  .pageview body {
    border-top: 1px solid #ccc;
    border-left: 1px solid #ccc;
    border-right: 2px solid #bbb;
    border-bottom: 2px solid #bbb;
    width: 648px !important;
    margin: 15px auto 25px;
    padding: 40px 50px;
  }
  /* IE6 */
  * html {
    overflow-y: scroll;
  }
  * html.pageview body {
    overflow-x: auto;
  }
  

  
    
    .writely-callout-data {
      display: none;
    }
    

    .writely-footnote-marker {
      background-image: url('MISSING');
      background-color: transparent;
      background-repeat: no-repeat;
      width: 7px;
      overflow: hidden;
      height: 16px;
      vertical-align: top;

      
      -moz-user-select: none;
    }
    .editor .writely-footnote-marker {
      cursor: move;
    }
    .writely-footnote-marker-highlight {
      background-position: -15px 0;
      -moz-user-select: text;
    }
    .writely-footnote-hide-selection ::-moz-selection, .writely-footnote-hide-selection::-moz-selection {
      background: transparent;
    }
    .writely-footnote-hide-selection ::selection, .writely-footnote-hide-selection::selection {
      background: transparent;
    }
    .writely-footnote-hide-selection {
      cursor: move;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }

  


  
  .br_fix span+br:not(:-moz-last-node) {
    
    position:relative;
    
    left: -1ex
    
  }

  
  #cb-p-tgt {
    font-size: 8pt;
    padding: .4em;
    background-color: #ddd;
    color: #333;
  }
  #cb-p-tgt-can {
    text-decoration: underline;
    color: #36c;
    font-weight: bold;
    margin-left: 2em;
  }
  #cb-p-tgt .spin {
    width: 16px;
    height: 16px;
    background: url(//ssl.gstatic.com/docs/clipboard/spin_16o.gif) no-repeat;
  }
}

h6 { font-size: 8pt }
h5 { font-size: 8pt }
h4 { font-size: 10pt }
h3 { font-size: 12pt }
h2 { font-size: 14pt }
h1 { font-size: 18pt }

blockquote {padding: 10px; border: 1px #DDD dashed }

.webkit-indent-blockquote { border: none; }

a img {border: 0}

.pb {
  border-width: 0;
  page-break-after: always;
  /* We don't want this to be resizeable, so enforce a width and height
     using !important */
  height: 1px !important;
  width: 100% !important;
}

.editor .pb {
  border-top: 1px dashed #C0C0C0;
  border-bottom: 1px dashed #C0C0C0;
}

div.google_header, div.google_footer {
  position: relative;
  margin-top: 1em;
  margin-bottom: 1em;
}


/* Table of contents */
.editor div.writely-toc {
  background-color: #f3f3f3;
  border: 1px solid #ccc;
}
.writely-toc > ol {
  padding-left: 3em;
  font-weight: bold;
}
ol.writely-toc-subheading {
  padding-left: 1em;
  font-weight: normal;
}
/* IE6 only */
* html writely-toc ol {
  list-style-position: inside;
}
.writely-toc-none {
  list-style-type: none;
}
.writely-toc-decimal {
  list-style-type: decimal;
}
.writely-toc-upper-alpha {
  list-style-type: upper-alpha;
}
.writely-toc-lower-alpha {
  list-style-type: lower-alpha;
}
.writely-toc-upper-roman {
  list-style-type: upper-roman;
}
.writely-toc-lower-roman {
  list-style-type: lower-roman;
}
.writely-toc-disc {
  list-style-type: disc;
}

/* Ordered lists converted to numbered lists can preserve ordered types, and
   vice versa. This is confusing, so disallow it */
ul[type="i"], ul[type="I"], ul[type="1"], ul[type="a"], ul[type="A"] {
  list-style-type: disc;
}

ol[type="disc"], ol[type="circle"], ol[type="square"] {
  list-style-type: decimal;
}

/* end default css */


  /* default print css */
  @media print {
    body {
      padding: 0;
      margin: 0;
    }

    div.google_header, div.google_footer {
      display: block;
      min-height: 0;
      border: none;
    }

    div.google_header {
      flow: static(header);
    }

    /* used to insert page numbers */
    div.google_header::before, div.google_footer::before {
      position: absolute;
      top: 0;
    }

    div.google_footer {
      flow: static(footer);
    }

    /* always consider this element at the start of the doc */
    div#google_footer {
      flow: static(footer, start);
    }

    span.google_pagenumber {
      content: counter(page);
    }

    span.google_pagecount {
      content: counter(pages);
    }

    .endnotes {
      page: endnote;
    }

    /* MLA specifies that endnotes title should be 1" margin from the top of the page. */
    @page endnote {
      margin-top: 1in;
    }

    callout.google_footnote {
      
      display: prince-footnote;
      footnote-style-position: inside;
      /* These styles keep the footnote from taking on the style of the text
         surrounding the footnote marker. They can be overridden in the
         document CSS. */
      color: #000;
      font-family: Verdana;
      font-size: 10.0pt;
      font-weight: normal;
    }

    /* Table of contents */
    #WritelyTableOfContents a::after {
      content: leader('.') target-counter(attr(href), page);
    }

    #WritelyTableOfContents a {
      text-decoration: none;
      color: black;
    }

    /* Comments */
    .writely-comment-yellow {
      background-color: #ffffd7;
    }
    .writely-comment-orange {
      background-color: #ffe3c0;
    }
    .writely-comment-pink {
      background-color: #ffd7ff;
    }
    .writely-comment-green {
      background-color: #d7ffd7;
    }
    .writely-comment-blue {
      background-color: #d7ffff;
    }
    .writely-comment-purple {
      background-color: #eed7ff;
    }
  }

  @page {
    @top {
      content: flow(header);
    }
    @bottom {
      content: flow(footer);
    }
    @footnotes {
      border-top: solid black thin;
      padding-top: 8pt;
    }
  }
  /* end default print css */


/* custom css */


/* end custom css */

/* ui edited css */

body {
  font-family: Verdana;
  
  font-size: 10.0pt;
  line-height: normal;
  background-color: #ffffff;
}
/* end ui edited css */


/* editor CSS */
.editor a:visited {color: #551A8B}
.editor table.zeroBorder {border: 1px dotted gray}
.editor table.zeroBorder td {border: 1px dotted gray}
.editor table.zeroBorder th {border: 1px dotted gray}


.editor div.google_header, .editor div.google_footer {
  border: 2px #DDDDDD dashed;
  position: static;
  width: 100%;
  min-height: 2em;
}

.editor .misspell {background-color: yellow}

.editor .writely-comment {
  font-size: 9pt;
  line-height: 1.4;
  padding: 1px;
  border: 1px dashed #C0C0C0
}


/* end editor CSS */

</style>

  
  <title>W9 Modele spójności</title>

</head>

<body 
    
    >
    
    
    
<div id=ss.b style=TEXT-ALIGN:left>
  <b style=COLOR:#3d85c6><font size=5>Modele spójności<br>
  </font></b><hr size=2><b style=COLOR:#3d85c6><font size=5><br>
  </font></b><b style=COLOR:#3d85c6><font size=3>Model spójności</font></b><br>
  <hr size=2>
</div>
<br>
<div id=ebim style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2502hpdrqzhp_b.png" style=HEIGHT:343px;WIDTH:500px>
</div>
<br>
Problem spójności danych istnieje w systemach stosujących zwielokrotnianie. Jeżeli dane są modyfikowane, to zmiana wprowadzona na pojedynczym węźle musi być przekazana do pozostałych, najlepiej zanim zlecony zostanie odczyt tych danych. W systemie rozproszonym wymiana danych na najniższym poziomie realizowana jest jednak zawsze z wykorzystaniem przesyłania komunikatów, które wprowadza opóźnienia. Propagacja modyfikacji nie może więc następować natychmiastowo, co może być wychwycone przez użytkowników obserwujących niespójności pomiędzy zawartościami poszczególnych replik. Model spójności określa „reguły gry” jakie będą stosowane przez system podczas aktualizacji danych. Są to pewne gwarancje, których udziela system w odniesieniu do uporządkowania operacji realizowanych w systemie rozproszonym. Aplikacje, dla których gwarancje te są wystarczające będą działały poprawnie pomimo istnienia zwielokrotniania, opóźnień i czasowych niespójności danych. Problem otwartym jest sposób wyrażenia tych gwarancji, czy innymi słowy tej „umowy” pomiędzy aplikacją a systemem. Mając zdefiniowany model spójności (reguły) należy skonstruować <i>protokół</i> <i>spójności</i> , który te reguły zrealizuje w systemie rozproszonym. Protokół określa kiedy i w jaki sposób należy ingerować w przetwarzanie, tak aby zdefiniowane na poziomie modelu własności były faktycznie zachowane.<br>
<a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-9-wyk-1.0-Slajd1 title=Sr-9-wyk-1.0-Slajd1> </a><br>
<br>
<b style=COLOR:#3d85c6><font size=3>Spójność ścisła</font></b><br>
<hr size=2><br>
<div id=c6ln style=TEXT-ALIGN:left>
  <img src="images/dcjpvv6n_2503gkz79pc9_b.png" style=HEIGHT:341px;WIDTH:500px><br>
  <br>
  W systemach scentralizowanych każdy odczyt zwraca wynik będący odzwierciedleniem <i>ostatniego</i> zapisu, co jest określane jako spójność ścisła (ang. <i>strict</i> <i>consistency</i> ). W systemie rozproszonym pojęcie <i>ostatni</i> jest niejednoznaczne, ponieważ nie ma jednego, globalnego zegara synchronizującego pracę poszczególnych węzłów. W efekcie może się zdarzyć, że operacja odczytu zwróci wynik sprzed ostatniego zapisu. Realizacja modelu przetwarzania charakterystycznego dla systemów scentralizowanych jest bardzo kosztowna, a niekiedy niemożliwa do zrealizowania. Najprostsza realizacja spójności ścisłej polega na zastosowaniu pojedynczego, centralnego serwera, który przetwarza wszystkie odwołania do danych. Realizacja taka jest oczywiście wysoce nieefektywna i nie korzysta z zalet jakie potencjalnie oferuje zwielokrotnianie. Stąd poszukuje się innych modeli spójności, które będą oferowały słabsze gwarancje, ale które będą mogły być dużo bardziej efektywnie implementowane.<br>
  <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-9-wyk-1.0-Slajd2 title=Sr-9-wyk-1.0-Slajd2> </a><br>
  <br>
  <font color=#3d85c6 size=3><b>Modele spójności replik</b></font><br>
  <hr size=2><br>
  <div id=h0r- style=TEXT-ALIGN:left>
    <img src="images/dcjpvv6n_2504g734brht_b.png" style=HEIGHT:341px;WIDTH:500px><br>
    <br>
    Generalnie modele spójności można podzielić na dwie podstawowe klasy: modele spójności nastawione na dane (ang. <i>data-centric</i> <i>consistency</i> <i>models</i> ) i modele spójności nastawione na klienta (<i>client-centric</i> <i>consistency</i> <i>models</i> ). Modele spójności nastawione na klienta będą prezentowane w ramach następnego wykładu.<br>
    <br>
    <p>
      Modele spójności nastawione na dane można podzielić dalej na dwie grupy: modele spójności przy dostępie ogólnym (ang. <i>general</i> <i>access</i> <i>consistency</i> <i>models</i> ) i modele spójności przy dostępie synchronizowanym (ang. <i>synchroni</i> <i>z</i> <i>ation</i> <i>access</i> <i>consistency</i> <i>models</i> ). Modele spójności przy dostępie ogólnym są bardziej „przyjazne” dla programisty, ponieważ program korzystający z tych modeli wygląda tak samo jak program pisany dla systemu scentralizowanego. Konsekwencją tego jest konieczność uspójniania danych podczas wykonywania każdej operacji modyfikującej. Rezygnację z pełnej przezroczystości dostępu do danych zastosowano w modelach przy dostępie synchronizowanym. W tej grupie modeli spójności występują specjalne operacje synchronizujące, dodawane do kodu programu, których wykonanie powoduje przeprowadzenie synchronizacji danych pomiędzy serwerami. Zwykłe dostępy do danych nie muszą powodować komunikacji z innymi serwerami. Podejście takie jest racjonalne w przypadku przeprowadzania przez aplikację serii aktualizacji, być może dotyczących tych samych zmiennych. Wyniki przeprowadzonych modyfikacji mogą w takim przypadku być przesłane łącznie.
    </p>
    <p>
      Modele spójności nastawione na dane były rozwijane głównie w ramach badań nad rozproszoną pamięcią dzieloną (ang. <i>Distributed</i> <i>Shared</i> <i>Memory</i> ).
    </p>
    <br>
    <br>
    <b style=COLOR:#3d85c6><font size=3>Modele spójności przy dostępie ogólnym</font></b><br>
    <hr size=2><br>
    <div id=w-8j style=TEXT-ALIGN:left>
      <img src="images/dcjpvv6n_2505g4n2prf7_b.png" style=HEIGHT:341px;WIDTH:500px><br>
      <br>
      Slajd powyższy wymienia główne modele spójności nastawione na dane przy dostępie ogólnym. Kolejność nie jest przypadkowa i (z grubsza) odzwierciedla siłę tych modeli. Spójność atomowa odpowiada działaniu systemu scentralizowanego – jest to więc najsilniejszy model, ale jednocześnie model wymuszający najmniej efektywną implementację. Spójność atomowa bywa też nazywana liniowością. Spójność sekwencyjna nadal jest bliska przetwarzaniu w systemie scentralizowanym, ale dopuszcza już pewne nakładanie się operacji w systemie, co potencjalnie może być wykorzystane do bardziej efektywnej pracy protokołu spójności. Spójność przyczynowa zachowuje porządek przyczynowy. Spójność PRAM porządkuje operacje zlecane przez poszczególne węzły. Spójność podręczna (zwana również koherencją) porządkuje operacje wykonywane na poszczególnych zmiennych. W końcu spójność procesorowa łączy w sobie własności spójności PRAM i podręcznej.<br>
      <br>
      <br>
      <b style=COLOR:#3d85c6><font size=3>Modele spójności przy dostępie synchronizowanym</font></b><br>
      <hr size=2><br>
      <div id=f7sp style=TEXT-ALIGN:left>
        <img src="images/dcjpvv6n_2506d9dg5cmt_b.png" style=HEIGHT:342px;WIDTH:500px><br>
        <br>
        Modele spójności przy dostępie ogólnym są wygodne w użyciu, gdyż nie wymagają modyfikacji przy przenoszeniu z systemu nie stosującego zwielokrotniania do systemu stosującego zwielokrotnianie. Niestety pomijając spójność atomową i sekwencyjną, pozostałe modele oferują własności, które często są niewystarczające do poprawnego działania aplikacji. Z drugiej strony realizacja nawet modelu sekwencyjnego zawsze obarczona jest bardzo dużym kosztem efektywnościowym. Poszukując innych rozwiązań zaproponowano modele o dostępie synchronizowanym, które są pewnego rodzaju kompromisem pomiędzy wygodą programisty a złożonością samego modelu. Z jednej bowiem strony programista jest zmuszany do uzupełnienia kodu programu o dodatkowe instrukcje, ale z drugiej strony te dodatkowe instrukcje „podpowiadają” systemowi kiedy jakie dane aplikacja będzie wykorzystywać, a więc kiedy należy je uspójniać. W efekcie protokoły spójności dla modeli przy dostępie synchronizowanym oferują efektywnie modele spójności zgodne z modelem sekwencyjnym (lub niekiedy atomowym), a jednocześnie charakteryzują się dużą efektywnością pozwalającą na praktyczne wdrożenie koncepcji DSM.<br>
        <br>
        <br>
        <b style=COLOR:#3d85c6><font size=3>Podstawowe założenia</font></b><br>
        <hr size=2><br>
        <div id=k07t style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2507cbf5vx8t_b.png" style=HEIGHT:345px;WIDTH:500px><br>
          <br>
          Rozważamy system składający się z <i>n</i> procesów, każdy pracujący na oddzielnym węźle. Procesy odwołują się do pamięci zorganizowanej w postaci zmiennych, współdzielonych przez wszystkie procesy. Dla uproszczenia rozważań zakładamy, że w systemie stosowana jest pełna replikacja, co oznacza, że każdy węzeł posiada pełną kopię całego zbioru zmiennych współdzielonych. Założenie to nie zmniejsza ogólności rozważań, bo nie wpływa na definicję modelu spójności, a jedynie na organizację rozproszonej pamięci.<br>
          <br>
          <p>
            Operacje realizowane na zmiennych współdzielonych są bądź odczytami bądź zapisami. Odczyt wartości <i>v</i> ze zmiennej <i>x</i> realizowany przez proces <i>pi</i> oznaczany będzie jako <i>ri(x)v</i> . Zapis wartości <i>v</i> do zmiennej <i>x</i> realizowany przez proces <i>pi</i> oznaczany będzie jako <i>wi(x)v</i> . Jeżeli kontekst stosowania wymienionych oznaczeń będzie jednoznaczny, to indeksy identyfikujące procesy zostaną pominięte.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Operacja odczytu bądź zapisu nie jest operacją atomową. Jest to szczególnie wyraziste w systemie rozproszonym, gdzie wykonanie operacji może oznaczać potrzebę komunikacji. W związku z tym w niektórych przypadkach będziemy rozważać jawne rozpoczęcie wykonywania operacji (zgłoszenie jej przez proces) i zakończenie wykonywania operacji (zwrócenie wyniku do procesu).
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Oznaczenia</font></b><br>
          <hr size=2><br>
          <div id=fop5 style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2508x3p3kzgv_b.png" style=HEIGHT:341px;WIDTH:500px><br>
            <br>
          </div>
          W definicjach modeli spójności zostaną użyte wymienione na slajdzie oznaczenia. Zapisy i odczyty zostały przedstawione na poprzednim slajdzie. Zbiór wszystkich operacji w systemie, zarówno zapisy jak i odczyty, będzie oznaczany przez <i>O</i> . Zbiór wszystkich operacji procesu <i>pi</i> będzie oznaczany przez <i>Oi</i> . Z punktu widzenia zarządzania spójnością najważniejsze są operacje zapisu <i>(</i> <i>OW</i> <i>),</i> bo to one muszą być powielone na wszystkich serwerach. Operacje wykonane na zmiennej <i>x</i> będą oznaczane jako <i>O|x</i> .<br>
          <br>
          <p>
            Procesy zlecają wykonywanie operacji sekwencyjnie. Liniowy porządek operacji zlecanych przez proces <i>pi</i> oznaczany będzie jako ?<i>i</i> . Porządek przyczynowy operacji wykonywanych w systemie będzie oznaczany zwykłą strzałką ?.<br>
          </p>
          <p>
            <br>
          </p>
          <p>
            Symbol ?<i>i</i> będzie oznaczać uporządkowanie operacji postrzeganych przez proces <i>pi</i> . Proces „widzi” swoje operacje, ale i również operacje innych procesów jeśli np. czyta wyniki zapisów tych procesów. Odczyt wartości zapisanej przez inny proces oznacza, że przed tym odczytem musi być zaszeregowany zapis tego procesu. Uporządkowanie operacji (uszeregowanie) postrzeganych przez poszczególne procesy może być różne, w zależności od ograniczeń nakładanych przez model spójności. Uszeregowanie określa porządek wykonywania operacji na zmiennych w konkretnym węźle.
          </p>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Definicja porządku przyczynowego</font></b><br>
          <hr size=2><br>
        </div>
        <div id=qmq3 style=TEXT-ALIGN:left>
          <img src="images/dcjpvv6n_2509fdkthsfm_b.png" style=HEIGHT:343px;WIDTH:500px><br>
          <br>
          Model spójności przyczynowej odwołuje się do definicji porządku przyczynowego. Porządek przyczynowy jest z kolei definiowany wymienionymi 3 warunkami. Po pierwsze: lokalne uporządkowanie operacji wykonywanych przez poszczególne procesy jest zachowywane przez porządek przyczynowy. Po drugie: jeżeli w jednym procesie następuje odczyt <i>r(x)v</i> , to oznacza, że zapis, który wprowadził do zmiennej <i>x</i> wartość <i>v</i> , czyli <i>w(x)v</i> musi poprzedzać ten odczyt w porządku przyczynowym. Co ważne: nie jest istotne na jakim węźle wykonywane są operacje odczytu i zapisu, a więc mogą być realizowane na różnych węzłach. Odczyt wartości zapisanej na innym węźle jest możliwy, jeżeli protokół aktualizacji danych prześle w międzyczasie komunikat aktualizujący. Ostatni warunek porządku przyczynowego jest domknięciem przechodnim relacji, mówiącym, że jeżeli operacja <i>o1</i> poprzedza przyczynowo jakąś operację <i>o</i> , a operacja <i>o</i> poprzedza przyczynowo <i>o2</i> , to wtedy <i>o1</i> poprzedza przyczynowo <i>o2</i> .<br>
          <br>
          <br>
          <b style=COLOR:#3d85c6><font size=3>Definicja uszeregowania legalnego</font></b><br>
          <hr size=2><br>
          <div id=w-3m style=TEXT-ALIGN:left>
            <img src="images/dcjpvv6n_2510c9rndjg7_b.png" style=HEIGHT:340px;WIDTH:500px><br>
            <br>
            Nie każde uszeregowanie operacji wykonanych w systemie rozproszonym jest możliwe do zrealizowania w praktyce. Będziemy rozważać tylko <b>uszeregowania</b> <b>legalne</b> . Legalność oznacza, że odczyt wartości <i>v</i> ze zmiennej <i>x</i> jest możliwy tylko wtedy, gdy nie było żadnego innego zapisu do zmiennej <i>x</i> wartości różnej od <i>v</i> , który znajdowałby się w uszeregowaniu procesu czytającego po zapisie wartości <i>v</i> a przed odczytem wartości <i>v</i> . Co więcej: nie może być miedzy zapisem wartości <i>v</i> a jej odczytem również operacji odczytu wartości innej niż <i>v</i> . Założenia te są dość intuicyjne jeżeli weźmiemy pod uwagę działanie pamięci lokalnej w węźle. Każda zmienna ma w pamięci swoją pojedynczą lokalizację i odczyt zwraca zawsze ostatnio zapisaną wartość.<br>
            <br>
            <p>
              Dla uproszczenia rozważań (nie redukując jednak ogólności rozważań) będziemy zakładać, że każdy zapis i odczyt dotyczy unikalnej wartości <i>v</i> . Innymi słowy, wartość zapisywana będzie jednoznacznie identyfikować konkretną operację zapisu.
            </p>
            <br>
            <br>
            <b style=COLOR:#3d85c6><font size=3>Definicja historii</font></b><br>
            <hr size=2><br>
            <div id=uup6 style=TEXT-ALIGN:left>
              <img src="images/dcjpvv6n_2511grsqjrcq_b.png" style=HEIGHT:342px;WIDTH:500px><br>
              <br>
              Analiza modeli spójności odwołuje się do pojęcia historii. Historia reprezentuje zrealizowane wcześniej przetwarzanie, a więc uporządkowany zbiór wszystkich operacji, które zostały wykonane.<br>
              <br>
              <p>
                Przetwarzanie każdego z procesów jest reprezentowane jego lokalną <b>historią</b> <i>hj</i> , która jest liniowo uporządkowanym zbiorem operacji zleconych przez ten proces. Relacją porządkującą jest lokalny porządek zleceń wykonania kolejnych operacji.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Złożenie historii wszystkich procesów daje <b>historię</b> <b>globalną</b> , gdzie relacją porządkującą jest relacja zależności przyczynowej (zawierająca w sobie lokalne porządki poszczególnych procesów). Zbiór ten jest częściowo uporządkowany, ponieważ niektóre zdarzenia realizowane są współbieżnie.<br>
              </p>
              <p>
                <br>
              </p>
              <p>
                Każdy z procesów postrzega w jakiś sposób zapisy, które zostały zgłoszone na innych węzłach. Uszeregowanie tych zapisów daje <b>obraz</b> <b>historii</b> <b>w</b> <b>procesie</b> . Obraz historii jest uporządkowany liniowo relacją lokalnego uszeregowania, które musi być legalne.
              </p>
              <p>
                Złożenie wszystkich lokalnych obrazów historii daje <b>obraz</b> <b>historii</b> , który jest kolekcją zbiorów liniowo uporządkowanych.
              </p>
              <br>
              <br>
              <b style=COLOR:#3d85c6><font size=3>Spójność sekwencyjna</font></b><br>
              <hr size=2><br>
              <div id=m.jf style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2512djd8mxfd_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                <br>
                Przetwarzanie jest zgodne z modelem spójności sekwencyjnej, jeżeli obraz historii w każdym z procesów spełnia oba zaprezentowane warunki. Pierwszy warunek mówi o tym, że lokalne uporządkowanie operacji powinno być zachowane w obrazie przetwarzania w każdym procesie. Dotyczy to oczywiście operacji wykonywanych w danym węźle oraz wszystkich zapisów, które zostały zgłoszone. Odczyty wykonywane na innych węzłach nie są brane pod uwagę, ponieważ są one realizowane jedynie lokalnie. Zapisy natomiast muszą być propagowane do wszystkich węzłów.<br>
                <br>
                <p>
                  Drugi warunek mówi o tym, że wszystkie zapisy w systemie muszą być globalnie uszeregowane. Innymi słowy: istnieje jedna, globalnie ustalona kolejność wykonywania <i>wszystkich</i> zapisów, które zostały zlecone w systemie. Zostało to zdefiniowane w ten sposób, że dla każdej pary operacji zapisu <i>w1</i> i <i>w2</i> wszystkie węzły albo realizują najpierw <i>w1</i> a później <i>w2</i> , albo najpierw <i>w2</i> a później <i>w1</i> . W skrócie można więc powiedzieć, że spójność sekwencyjna wymusza globalne uporządkowanie zapisów.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Spójność sekwencyjna - przykład</font></b><br>
                <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-9-wyk-1.0-Slajd11 title=Sr-9-wyk-1.0-Slajd11> </a><br>
              </div>
              <div id=cv31 style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2513d5jxk4fs_b.png" style=HEIGHT:344px;WIDTH:500px><br>
                <br>
                Przykład przedstawia przetwarzanie w systemie, który gwarantuje spójność sekwencyjną. Ostateczna postać obrazów historii w procesach <i>p1</i> i <i>p2</i> spełnia oba warunki modelu. W szczególności warto zwrócić uwagę na globalne uporządkowanie operacji zapisu: oba procesy widzą najpierw zapis wartości 1 do zmiennej <i>x</i> , a później wartości 2. W obrazach historii w procesie <i>p1</i> występuje dodatkowo odczyt, który nie występuje w obrazie historii procesu <i>p2</i> . Komunikat przesyłany z procesu <i>p2</i> do <i>p1</i> oznacza aktualizację danych.<br>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Algorytm <i>fast-read</i></font></b><br>
                <hr size=2><br>
                <div id=lm41 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2514ct8dkdgb_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                  <br>
                  <p>
                    Realizacja modelu spójności wymaga zaprojektowania odpowiedniego protokołu spójności. Przytoczony na przykładzie algorytm jest jednym z możliwych protokołów gwarantujących zachowanie spójności sekwencyjnej. Jak sama nazwa wskazuje preferuje on odczyty. Preferencja przejawia się tym, że odczyt nigdy nie jest blokowany – od razu zwracana jest lokalnie przechowywana wartość zmiennej.
                  </p>
                  <p>
                    Zapis algorytmu ma postać procedur obsługi zdarzeń. Zawartość pamięci reprezentowana jest w algorytmie jako tablica <i>M</i> , zwielokrotniona w postaci lokalnych tablic <i>Mi</i> w procesie <i>pi</i>.
                  </p>
                  <p>
                    <br>
                  </p>
                  <p>
                    Odczyt zwraca po prostu wartość przechowywaną na odpowiedniej pozycji w tablicy <i>M</i> . Zlecenie zapisu jest rozgłaszane (lub rozsyłane) do wszystkich procesów. Rozgłaszanie jest rozgłaszaniem niepodzielnym (ang. <i>atomic</i> <i>broadcast</i> ), co oznacza, że komunikat musi dotrzeć do wszystkich i to w tej samej kolejności. Warstwa komunikacji grupowej zajmie się więc w tym przypadku zapewnieniem uporządkowania operacji zapisu. Jest to wygodna (choć nie zawsze najbardziej efektywna) metoda implementacji protokołu spójności. Właściwa operacja modyfikacji zmiennej realizowana jest w procedurze obsługi odbioru wiadomości aktualizacyjnej. Dotyczy to również węzła, który inicjuje zapis. Jest to ważne, ponieważ zapisy mają być wszędzie realizowane w tej samej kolejności. Zapis powoduje wstrzymanie przetwarzania procesu, który go zleca, do czasu zakończenia niepodzielnego rozgłaszania. Wykonanie bieżącego zapisu może być więc poprzedzone wcześniejszym obsłużeniem zapisów zleconych na innych węzłach – o kolejności zadecyduje warstwa komunikacyjna. W procedurze obsługi odbioru wiadomości aktualizacyjnej, jeżeli komunikat dociera do procesu, który inicjował rozgłoszenie, następuje obudzenie procesu zlecającego (funkcja <i>signal</i> ). Proces był zawieszony w procedurze zapisu (funkcją <i>wait</i> ).
                  </p>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Algorytm <i>fast-write</i></font></b><br>
                  <hr size=2>
                </div>
                <br>
              </div>
              <div id=t8xk style=TEXT-ALIGN:left>
                <img src="images/dcjpvv6n_2515dws625d9_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                <br>
                Protokół <i>fast-write</i> dla spójności sekwencyjnej optymalizuje operacje zapisu wykonywane w systemie. Ich wykonanie nigdy nie jest blokujące, co pozwala na natychmiastową kontynuację obliczeń, być może powodującą wykonanie kolejnego zapisu. Blokowaniu natomiast podlega operacja odczytu. Sprawdza ona czy licznik <i>num</i> , inkrementowany przy każdym zapisie osiągnął wartość 0, co oznacza poprawne zakończenie wszystkich operacji zapisu zleconych lokalnie. Proces może zlecić wiele zapisów, jeden za drugim, zwiększając w ten sposób zmienną <i>num</i> . Warstwa komunikacyjna będzie próbowała dostarczyć odpowiednie komunikaty do wszystkich serwerów, a proces w tym czasie może realizować dalsze zadania. Odczyt wymaga zakończenia wykonywania wszystkich dotychczasowych operacji zapisu zleconych lokalnie. Bez tego oczekiwania mogłoby dojść do wygenerowania uszeregowania nielegalnego, np.: w(x)5 ? r(x)0. Obsługa zapisu wymaga w tym przypadku rozgłaszania niepodzielnego zachowującego porządek FIFO, gdyż w przeciwnym wypadku mogłoby dość do przestawienia kolejności zapisów zleconych przez pojedynczy proces, a więc doszłoby do naruszenia lokalnego uporządkowania. Protokół <i>fast-read</i> nie wymagał stosowania niepodzielnego rozgłaszania FIFO, ponieważ przed zleceniem kolejnego zapisu poprzedni musiał być zakończony, co wymuszało zachowanie lokalnego porządku.<br>
                <br>
                <p>
                  Przedstawione protokoły dla spójności sekwencyjnej pokazują, że jej realizacja jest kosztowna. Koszt objawia się w tym przypadku opóźnieniami, które wynikają z koniecznej synchronizacji procesów. W zależności od potrzeb można optymalizować operacje odczytu bądź zapisu, ale zawsze takie optymalizacje odbywają się kosztem drugiej operacji.
                </p>
                <br>
                <br>
                <b style=COLOR:#3d85c6><font size=3>Spójność atomowa</font></b><br>
                <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-9-wyk-1.0-Slajd14 title=Sr-9-wyk-1.0-Slajd14> </a><br>
                <div id=lf79 style=TEXT-ALIGN:left>
                  <img src="images/dcjpvv6n_2516hhr577cc_b.png" style=HEIGHT:345px;WIDTH:500px><br>
                  <br>
                  Spójność atomowa jest silniejszym modelem niż spójność sekwencyjna. W jej przypadku brane są bowiem pod uwagę zależności czasowe pomiędzy zdarzeniami na różnych węzłach. Warunki, które muszą spełniać obrazy historii przetwarzania na poszczególnych węzłach są bardzo podobne do tych dla spójności sekwencyjnej. Drugi warunek jest identyczny. W pierwszym zamiast lokalnego porządku występuje zależność czasowa pomiędzy zdarzeniami. Oczywiście synchronizacja przetwarzania z uwzględnieniem zależności czasowych jest dużo bardziej kosztowna i wymaga dodatkowej komunikacji.<br>
                  <br>
                  <br>
                  <b style=COLOR:#3d85c6><font size=3>Spójność atomowa - przykład</font></b><br>
                  <hr size=2><br>
                  <div id=o0bz style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2517d6ssrtg7_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    Rysunek przedstawia tą samą sytuację, która była prezentowana w przypadku spójności sekwencyjnej. W tym przypadku jednak uzyskanie takich samych obrazów historii przetwarzania wymaga „przesunięcia” zapisu w(x)2 tak, aby w czasie rzeczywistym występował po odczycie <i>r(x)1</i> w procesie <i>p1</i>.
                    <p>
                    <br>
                    </p>
                    <p>
                    Spójność atomowa w praktyce nie jest realizowana. Jej znaczenie wiąże się głównie z wykorzystaniem do formalnej weryfikacji algorytmów.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność przyczynowa</font></b><br>
                    <hr size=2><br>
                    <div id=q8bi style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2518f5dkjnss_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    Pamięć spójna przyczynowo musi zachowywać porządek przyczynowy operacji. Jeżeli więc operacja <i>o2</i> zależy przyczynowo od <i>o1</i> , to we wszystkich lokalnych obrazach przetwarzania operacje te powinny występować właśnie w tej kolejności. W praktyce można to wyrazić następująco:
                    <p>
                    <br>
                    </p>
                    <p>
                    <i>Zapisy</i> <i>potencjalnie</i> <i>powiązane</i> <i>przyczynowo</i> <i>muszą</i> <i>być</i> <i>widziane</i> <i>przez</i> <i>wszystkie</i> <i>procesy</i> <i>w</i> <i>takim</i> <i>samym</i> <i>porządku</i> <i>.</i> <i>Zapisy</i> <i>współbieżne</i> <i>mogą</i> <i>być</i> <i>na</i> <i>różnych</i> <i>maszynach</i> <i>oglądane</i> <i>w</i> <i>różnej</i> <i>kolejności</i> <i>.</i>
                    </p>
                    <p>
                    <i><br>
                    </i>
                    </p>
                    <p>
                    Implementacja spójności przyczynowej musi przechowywać informacje o zależnościach przyczynowych pomiędzy operacjami. Można do tego celu wykorzystać wektorowe znaczniki czasu.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    <b style=COLOR:#3d85c6><font size=3>Spójność przyczynowa - przykłady</font></b><br>
                    </p>
                    <hr size=2>
                    <p>
                    <br>
                    </p>
                    <p>
                    </p>
                    <div id=g4ce style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2519gmk4tngw_b.png" style=HEIGHT:344px;WIDTH:500px><br>
                    <br>
                    Na slajdzie pokazano przykładowe przetwarzanie w systemie zachowującym przyczynowe uporządkowanie operacji. Każdy z procesów w swoim obrazie przetwarzania musi umieścić wszystkie lokalne operacje oraz wszystkie operacje zapisu, zachowując przy tym warunek legalności. Pierwsze zapisy do zmiennej <i>x</i> realizowane przez oba procesy <i>p1</i> i <i>p2</i> są realizowane współbieżnie, nie są od siebie zależne przyczynowo. W efekcie ich wyniki mogą być obserwowalne na węzłach w różnej kolejności. Tak też się stało w tym przypadku. Proces <i>p1</i> odczytuje z <i>x</i> wartość 1, co oznacza, że zapis tej wartości musiał wystąpić po zapisie <i>w(x)2</i> (inaczej naruszony byłby warunek legalności – odczytywana byłaby wartość nadpisana). W procesie <i>p2</i> następuje odczyt z <i>x</i> wartości 2, co oznacza, że odpowiedni zapis musiał trafić po <i>w(x)1</i> . W efekcie procesy <i>p1</i> i <i>p2</i> widzą oba zapisy do <i>x</i> w różnej kolejności. Jest to jak najbardziej dopuszczalne, ponieważ zapisy te były realizowane współbieżnie.<br>
                    <br>
                    <p>
                    Warto zauważyć, że powyższa realizacja nie jest spójna sekwencyjnie. W modelu sekwencyjnym <i>wszystkie</i> zapisy powinny być postrzegane przez <i>wszystkie</i> procesy w tej samej kolejności.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Protokół dla spójności przyczynowej</font></b><br>
                    <hr size=2>
                    </div>
                    <br>
                    <p>
                    </p>
                    <div id=a5z5 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2520gmj429gk_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                    <br>
                    Slajd przedstawia przykładowy protokół realizujący model spójności przyczynowej. Do jego implementacji wykorzystano rozgłaszanie zachowujące uporządkowanie przyczynowe (funkcja <i>causal_broadcast</i> ), a więc cały ciężar realizacji protokołu spada w tym przypadku na warstwę komunikacji grupowej. Warto zwrócić uwagę, że zarówno operacje odczytu jak i zapisu nie wymagają w tym przypadku blokowania, synchronizującego przetwarzanie z operacjami na innych węzłach. Zarówno zapis jak i odczyt może być wykonywany z pełną szybkością. Przetwarzanie lokalne zmiennych zawsze generuje realizacje zachowujące legalność ponieważ zapisy od razu są odnotowywane w pamięci, co powoduje, że następujące po nich odczyty zwracają zapisaną wartość. Komunikaty rozgłoszeniowe są ignorowane przez węzły, które wysyłają odpowiednie aktualizacje.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność PRAM</font></b><br>
                    <hr size=2><br>
                    <div id=veva style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2521c9v8vtgm_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                    <br>
                    Spójność PRAM (ang. <i>pipelind</i> <i>RAM</i> ) jest modelem słabszym od spójności przyczynowej. Dla zapewnienia spójności PRAM wystarczy w obrazach historii każdego procesu zachować lokalny porządek wykonywania operacji każdego innego procesu. Nazwa <i>pipelined</i> oczywiście nie jest tu przypadkowa – chodzi o potok zleceń płynących od danego procesu. Potok ten musi zachowywać oryginalne uporządkowanie.<br>
                    <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-9-wyk-1.0-Slajd20 title=Sr-9-wyk-1.0-Slajd20> </a><br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność PRAM - przykład</font></b><br>
                    <hr size=2><br>
                    <div id=x1ie style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2522f42md5fq_b.png" style=HEIGHT:344px;WIDTH:500px><br>
                    <br>
                    <p>
                    Na slajdzie pokazano przykładowe przetwarzanie w systemie zachowującym spójność PRAM. Zaznaczone operacje są uwzględniane w obrazie historii procesu <i>p3</i> . Zapisy <i>w(x)1</i> i <i>w(x)2</i> realizowane są przez różne procesy, w związku z czym mogą być wykon ywane w procesie <i>p3</i> w dowolnej kolejności. W przypadku przetwarzania z rysunku zapis <i>w(x)2</i> dociera do <i>p3</i> przed zapisem zapisem <i>w(x)1</i> . Z punktu widzenia modelu spójności PRAM ważne jest jednak to, że zapisy <i>w(x)1</i> i <i>w(y)1</i> są widziane w kolejności, w której były wykonywane przez <i>p1</i>.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    Warto zauważyć, że zapisy <i>w(x)1</i> i <i>w(x)2</i> są od siebie zależne przyczynowo. Łączy je odczyt zmiennej <i>y</i> zapisywanej przez <i>p1</i> . W obrazie historii w procesie <i>p3</i> operacje te występują jednak w odwrotnej kolejności. W związku z tym przedstawione przetwarzanie nie zachowuje spójności przyczynowej.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Protokół dla spójności PRAM</font></b><br>
                    <hr size=2><br>
                    <div id=t5.t style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2523hb6zsbdx_b.png" style=HEIGHT:340px;WIDTH:500px><br>
                    <br>
                    Protokół spójności dla modelu PRAM jest bardzo podobny do protokołu spójności dla spójności przyczynowej. Jedna różnica polega na zastąpieniu rozgłaszania zachowującego porządek przyczynowy (<i>causal_broadcast</i> ) rozgłaszaniem zachowującym kolejność wysyłania komunikatów rozgłoszeniowych danego procesu (ang. <i>FIFO</i> <i>broadacst</i> ). Oczywiście realizacja funkcji <i>FIFO_broadcast</i> jest znacznie „tańsza” niż realizacja funkcji <i>causal_broadcast</i> , ale też model PRAM oferuje mniej niż spójność przyczynowa. W tym przypadku również operacje zapisu i odczytu nie są blokowane, co oczywiście pozytywnie wpływa na efektywność.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność podręczna</font></b><br>
                    <hr size=2><br>
                    <div id=hyy3 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2524fsq3zgdw_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    Spójność podręczna (ang. <i>cache</i> <i>consistency</i> ) jest modelem, w którym zachowany jest globalny porządek operacji zapisu do poszczególnych zmiennych. Część wspólna zbiorów <i>OW</i> i <i>O|x</i> reprezentuje wszystkie zapisy w systemie dotyczące zmiennej <i>x</i> . Obrazy historii przetwarzania we wszystkich procesach powinny umieszczać te zapisy w tej samej kolejności. Model ten nie wymaga, aby zachowane było lokalne uporządkowanie operacji o ile dotyczą one różnych zmiennych. Jest to więc model, który jest całkowicie niezależny do spójności PRAM i spójności przyczynowej.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność podręczna - przykłady</font></b><br>
                    <hr size=2><br>
                    <div id=bmnu style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2525g6zqd6c2_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                    <br>
                    Slajd przedstawia przykładowe przetwarzanie w systemie zachowującym spójność podręczną. Jak ławo zauważyć operacje zapisu wykonywane na zmiennej <i>x</i> są widziane przez oba procesy w tej samej kolejności. Zmienna <i>y</i> nie wnosi tu nic nowego, ponieważ jest tylko jeden zapis. Warto jednak zwrócić uwagę na uporządkowanie wszystkich zapisów w obrazach historii przetwarzania. Widać z niego, że nie jest zachowywany porządek lokalny. Proces <i>p2</i> widzi zapis do zmiennej <i>y</i> przez zapisem <i>w(x)2</i> , odwrotnie niż proces <i>p1</i> . Tym bardziej więc nie jest zachowywany porządek przyczynowy, co widać w sekwencji operacji <i>w1(x)2</i>&nbsp;? <i>w1(y)1</i>&nbsp;? <i>r2(y)1</i>&nbsp;? <i>r2(x)1</i> .<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Protokół dla spójności podręcznej</font></b><br>
                    <hr size=2><br>
                    <div id=u:cp style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2526fqvnsrcw_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    Protokół spójności <i>fast-read</i> dla spójności podręcznej przypomina analogiczny protokół dla spójności sekwencyjnej. W tym przypadku następuje również blokowanie podczas realizacji zapisu, ponieważ zapisy te muszą być uporządkowane względem innych zapisów do tych samych zmiennych. W przeciwieństwie do poprzedniego protokołu nie występuje tu jednak pełna wersja rozgłaszania niepodzielnego, porządkującego globalnie wszystkie komunikaty, ale jego wersja uproszczona, porządkująca komunikaty aktualizujące wybraną zmienną. W literaturze rozgłoszenie takie nie jest jakoś specjalnie nazywane, stąd w zapisie protokołu użyto nazwy <i>atomicx_broadcast</i> , dla odróżnienia od <i>atomic_broadcast</i> . Oczywiście realizacja <i>atomicx_broadcast</i> jest mniej kosztowna od pełnego niepodzielnego rozgłaszania, stąd protokół <i>fast-write</i> dla spójności podręcznej powinien charakteryzować się większą wydajnością od analogicznego protokołu dla spójności sekwencyjnej. Rozgłoszenie <i>atomicx_broadcast</i> może być koordynowane współbieżnie przez różne procesy, o ile dotyczy różnych zmiennych. Jego implementacja może więc być bardziej rozproszona, a więc lepiej wykorzystująca dostępne zasoby.<br>
                    <br>
                    <br>
                    <div id=adh- style=TEXT-ALIGN:left>
                    <div id=w_du style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2528gxdzxxhm_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                    <br>
                    </div>
                    Przez analogię można również skonstruować protokół <i>fast-write</i> dla spójności podręcznej, który strukturalnie jest identyczny z protokołem <i>fast-write</i> dla spójności sekwencyjnej. W tym przypadku również blokowanie zostaje przeniesione do operacji odczytu. Blokowaniu podlegają jednak jedynie operacje odczytu, które odwołują się do zmiennych, dla których nie dokończono jeszcze realizacji ostatnich operacji zapisu. W celu stwierdzenia, które operacje wymagają synchronizacji, protokół przechowuje tablicę liczników <i>num</i> , w której <i>i-ta</i> pozycja reprezentuje liczbę aktualnie realizowanych zapisów na <i>i-tej</i> zmiennej. Wyzerowanie licznika powoduje zniesienie blokowania oczekującego zapisu.<br>
                    <br>
                    <p>
                    W protokole <i>fast-write</i> zapisy nie są blokowane. W związku z tym jest możliwość zlecenia wielu zapisów, które będą realizowane w tle. W szczególności możliwe jest zlecenie wielu zapisów do tej samej zmiennej. Zapisy do tych samych zmiennych powinny być jednak porządkowane, dlatego do rozgłaszania zleceń zapisu użyto rozgłaszania uporządkowanego FIFO, ale nie w pełnej wersji, a jedynie w odniesieniu do poszczególnych zmiennych. Podobnie jak poprzednio, implementacja rozgłaszania porządkującego zapisy do pojedynczych zmiennych jest prostsza do zrealizowania od rozgłaszania porządkującego wszystkie komunikaty.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność procesorowa</font></b><br>
                    <hr size=2>
                    </div>
                    <br>
                    </div>
                    <div id=z8in style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2529fn2wxwhg_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    Spójność procesorowa nie wprowadza kompletnie nowej jakości. Jest to po prostu połączenie spójności PRAM i podręcznej. Definicja modelu spójności zawiera warunki, które były wymieniane w definicjach modeli PRAM i spójności podręcznej. W skrócie pamięć jest spójna procesorowo, jeżeli lokalny porządek zlecania operacji w poszczególnych procesach jest zachowany w obrazach historii przetwarzania wszystkich procesów (PRAM), oraz gdy zapisy do poszczególnych zmiennych są globalnie uporządkowane (spójność podręczna).<br>
                    <a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-9-wyk-1.0-Slajd27 title=Sr-9-wyk-1.0-Slajd27> </a><br>
                    </div>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność procesorowa - przykład</font></b><br>
                    <hr size=2>
                    </div>
                    <br>
                    </div>
                    <div id=iotq style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2530d866z7gx_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    Rysunek przedstawia przykładowe wykonanie w systemie zachowującym spójność procesorową. Jak widać z rysunku w obrazach historii obu procesów zapisy do zmiennej <i>x</i> widziane są w tej samej kolejności. Uporządkowanie zleceń z poszczególnych procesów również jest zachowane. Nie oznacza to jednak, że istnieje jeden, globalny porządek wykonywania operacji zapisu (co oznaczałoby efektywnie, że spełnione są wymagania modelu sekwencyjnego). Zapisy <i>w(x)1</i> i <i>w(y)1</i> występują w obrazach historii procesów w odwrotnej kolejności.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Protokół dla spójności procesorowej</font></b><br>
                    <hr size=2>
                    </div>
                    <br>
                    </div>
                    <div id=w3h6 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2531cv28hhc3_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    Slajd przedstawia protokół spójności typu <i>fast-write</i> dla spójności procesorowej. Struktura protokołu jest identyczna z poprzednimi protokołami <i>fast-write</i> . Różnica polega na specyficznej metodzie rozgłaszania zleceń aktualizacji danych. Rozgłaszanie to, oznaczone jako <i>FIFO_atomicx_broadcast</i> porządkuje globalnie wszystkie zapisy pojedynczych procesów oraz porządkuje globalnie zapisy odnoszące się do tych samych zmiennych. Zapisy nie są blokowane. Aktualizacje realizowane są po odebraniu komunikatu aktualizacyjnego. Odczyty mogą być blokowane, gdy dotyczą zmiennej, której aktualizacja zlecona przez ten węzeł jest jeszcze realizowana.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Naruszanie porządku przyczynowego</font></b><br>
                    <hr size=2><br>
                    <div id=m3li style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2532fczkwcgg_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    Przykład na slajdzie pokazuje realizację w systemie zachowującym spójność procesorową, w której naruszona jest jednak spójność przyczynowa. Proces <i>p3</i> dokonuje na początku odczytu ze zmiennej <i>y</i> , której aktualizacja dociera do tego procesu jako pierwsza. Następnie docierają do tego procesu dwie aktualizacje zmiennej <i>x</i> , które są obserwowane kolejnymi odczytami. Okazuje się jednak, że zapis <i>w(y)1</i> w procesie <i>p2</i> jest przyczynowo zależny od wcześniejszych zapisów do zmiennej <i>x</i> realizowanych przez proces <i>p1</i> . Zależność ta nie jest jednak uwzględniana przy propagacji zapisów do procesu <i>p3</i> . Wskazuje to jednoznacznie na rozróżnialność spójności przyczynowej i procesorowej.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Relacje pomiędzy modelami spójności</font></b><br>
                    <hr size=2><br>
                    <div id=dldm style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2533cdnghzhr_b.png" style=HEIGHT:344px;WIDTH:500px><br>
                    <br>
                    Omówione modele spójności przy dostępie ogólnym są w pewnych zależnościach między sobą. Idąc od dołu, a więc od modeli najmniej restrykcyjnych mamy model PRAM, gwarantujący zachowanie porządku lokalnego wykonywanych operacji przez poszczególne procesy. Rozszerzając zachowywany porządek lokalny modelu PRAM o uporządkowanie przyczynowe dostajemy spójność przyczynową. Spójność podręczna wymaga uporządkowania, które jest całkowicie ortogonalne w stosunku do wymagań spójności PRAM czy przyczynowej. Łącząc własności spójności PRAM i spójności podręcznej dostajemy spójność procesorową. Jeżeli wszystkie zapisy w systemie są globalnie uporządkowane, a więc obserwowane przez wszystkie procesy w tej samej kolejności, to dostajemy model sekwencyjny, który jest silniejszy zarówno od spójności przyczynowej jak i procesorowej. Ostatecznie uwzględnienie w uporządkowaniu globalnym kolejności występowania zdarzeń w czasie rzeczywistym prowadzi do modelu atomowego, który jest z kolei silniejszy od modelu sekwencyjnego.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Dostęp synchroniczny - założenia</font></b><br>
                    <hr size=2><br>
                    <div id=dx6j style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2534cg536bcw_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    Drugą grupę modeli spójności w ramach modeli nastawionych na dane tworzą modele przy dostępie synchronizowanym. Modele te próbują zaradzić niedogodnościom modeli przy dostępie swobodnym, w których albo protokół okazywał się być nieefektywny (spójność atomowa i sekwencyjna), albo oferowane własności uszeregowania zapisów były niewystarczające do działania aplikacji. Niekiedy może się okazać nawet, że modele słabsze (spójność przyczynowa, PRAM czy podręczna) są wystarczające do konkretnych algorytmów, ale wykazanie tej wystarczalności jest zadaniem bardzo trudnym. Powoduje to zrozumiałą niechęć programistów do stosowania słabszych modeli spójności.<br>
                    <br>
                    <p>
                    Rozwiązaniem zaproponowanym przez twórców niektórych systemów z rozproszoną pamięcią dzieloną jest propozycja kompromisu pomiędzy wygodą programowania takich systemów a efektywnością ich pracy. Modele przy dostępie ogólnym nie wymagają żadnej zmiany kodu algorytmu – program powinien działać poprawnie bez modyfikacji, niestety nieefektywnie. Jeżeli zrezygnować z pełnej transparentności i wymusić na programiście oznakowanie kodu dodatkowymi instrukcjami podpowiadającymi systemowi jakie są oczekiwania co do spójności danych, to implementacja odpowiedniego protokołu spójności może się okazać dużo bardziej efektywna. Jeżeli tylko dodatkowe instrukcje i ich umiejscowienie będzie proste, to rozwiązanie takie ma szansę na popularyzację.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    Kolejne slajdy prezentują modele spójności przy dostępie synchronizowanym. Model systemu pozostaje taki jak poprzednio. Działania wykonywane są więc przez zbiór <i>n</i> procesów rozlokowanych na <i>n</i> węzłach. Procesy wykonują operacje na zbiorze zmiennych współdzielonych, których repliki znajdują się na każdym węźle. Dodatkowo istnieje zbiór <i>S</i> obiektów synchronizujących. W zależności od modelu wykorzystywane są następujące obiekty synchronizujące: zamki i bariery. Na zamkach wykonywane są dwie operacje: <i>acquire</i> – zajęcie (nabycie) zamka i <i>release</i> – zwolnienie zamka. Dla bariery wykonuje się operację synchronizacji na barierze. Synchronizacja taka polega na wstrzymaniu przetwarzania procesów zgłaszających się do bariery do czasu zgłoszenia się wszystkich procesów.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność słaba</font></b><br>
                    <hr size=2><br>
                    <div id=pr5r style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2535gvc6wbdw_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    </div>
                    Pierwszym modelem spójności przy dostępie synchronizowanym była <b>spójność</b> <b>słaba</b> (ang. <i>weak</i> <i>consistency</i> ). W modelu tym rozróżniono po raz pierwszy dwa typy operacji: operacje dostępu do danych współdzielonych i operacje na zmiennych synchronizujących. Podstawową motywacją dla wprowadzenia jawnej operacji synchronizującej było umożliwienie opóźnienia propagacji aktualizacji do innych węzłów do czasu aż to będzie faktycznie potrzebne. W modelu sekwencyjnym praktycznie każda, najmniejsza operacja zmusza system do podejmowania kroków zmierzających do uspójnienia danych. Niekiedy jednak logika algorytmu wskazuje, że dane będą odczytywane później, po zaktualizowaniu większej grupy zmiennych. W spójności słabej zapisy do zmiennych współdzielonych nie muszą być od razu propagowane. Można je zbuforować i przesłać łącznie podczas wykonywania operacji synchronizującej.<br>
                    <br>
                    <p>
                    W spójności słabej wyróżnia się jeden typ operacji synchronizującej. Definicja spójności słabej mówi, że:<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    1) Operacje na zmiennych synchronizujących są spójne atomowo (w nowszym podejściu sekwencyjnie). Wykonując operację synchronizującą proces może więc uzyskać gwarancję, że jego wcześniejsze modyfikacje na pewno dotrą do pozostałych procesów.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    2) Nie można wykonać (zakończyć) operacji dostępu do zmiennej synchronizującej przed globalnym zakończeniem wcześniejszych operacji dostępu do zmiennych współdzielonych. Chodzi o to, żeby operacja synchronizująca swoim działaniem objęła wszystkie wcześniej wykonane operacje danego procesu.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    3) Nie można wykonać (zakończyć) operacji dostępu do zmiennej współdzielonej przed globalnym zakończeniem wcześniejszych operacji dostępu do zmiennych synchronizujących. Motywacją w tym przypadku jest uniemożliwienie np. odczytywania danych, jeżeli dane te nie zostały jeszcze zaktualizowane, ponieważ operacja synchronizująca cały czas jest jeszcze wykonywana.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność słaba - przykład</font></b><br>
                    <hr size=2><br>
                    <div id=qs4w style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2536dbnrg6g3_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    Procesy <i>p1</i> i <i>p2</i> wykonują zapisy do zmiennej <i>x</i> współbieżnie, bez żadnej synchronizacji ze sobą. Następnie oba procesy wykonują operację synchronizującą, która powinna spowodować wymianę informacji pomiędzy węzłami odnośnie nowych operacji, o których druga strona nie wie. W efekcie zlecone wcześniej zapisy trafiają do drugiego serwera. Odczyty, które następują po synchronizacji odzwierciedlają w takiej sytuacji zapisy wykonane na zdalnym serwerze.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność zwalniana</font></b><br>
                    <hr size=2><br>
                    <div id=g2h7 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2537dk2d3xdb_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    Kolejny model spójności to spójność zwalniania (ang. <i>release</i> <i>consistency</i> ). Model ten udoskonalił spójność słabą poprzez rozróżnienie dwóch oddzielnych operacji synchronizujących wykonywanych na zamkach. Operacje te w swojej logice działają podobnie do semaforów, umożliwiając realizację wzajemnego wykluczania. Dodatkowo podczas ich wykonywania następuje propagacja zmian do pozostałych serwerów. Operacja bariery służy do globalnej synchronizacji całej pamięci na wszystkich węzłach.<br>
                    <br>
                    <p>
                    Rozróżniamy dwa istotnie różne protokoły spójności dla spójności zwalniania; protokoły, które były niekiedy mylnie nazywane modelami spójności. Otóż w protokole <i>eager</i> <i>release</i> węzeł, który wykonuje operację zwalniania zamka rozsyła jednocześnie informację aktualizującą do wszystkich pozostałych serwerów. Do czasu wykonania operacji <i>release</i> żadna komunikacja nie jest potrzebna. Sama informacja aktualizacyjna może mieć postać aktualizacji bezpośrednio danych lub może powodować unieważnienie replik.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    Drugi protokół to <i>lazy</i> <i>release</i> , w którym stosuje się właśnie podejście <i>leniwe</i> . W przeciwieństwie do protokołu <i>eager</i> nie wysyła się aktualizacji do wszystkich, bo najprawdopodobniej wszyscy ich nie potrzebują. Aktualizacja danych jest tu opóźniona do czasu wykonania następnej operacji <i>acquire</i> . W tym momencie bowiem wiadomo, kto tych danych potrzebuje. Synchronizacja następuje więc pomiędzy dwoma konkretnymi serwerami: tym, który dokonywał ostatnich modyfikacji (posiada więc aktualną kopię) i tym, który potrzebuje te dane. Jest to rozwiązanie bardzo oszczędne komunikacyjnie, ponieważ angażuje tylko węzły, które muszą być w tej sytuacji angażowane. Niestety pewnym problemem staje się w tym podejściu kumulacja informacji o wcześniejszym przetwarzaniu. Każdy kolejny węzeł musi bowiem uczestniczyć w przenoszeniu informacji o modyfikacjach, zarówno tych, które on sam dokonał, jak i tych wykonanych przez wszystkie węzły, które uczestniczyły w przetwarzaniu.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność zwalniana - przykład</font></b><br>
                    <hr size=2><br>
                    </div>
                    <div id=icsh style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2538c4585tg5_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    Rysunek pokazuje przykładowe przetwarzanie w systemie stosującym spójność zwalniania. Odczyty realizowane przez proces <i>p2</i> przed operacją <i>acquire</i> zwracają wartości początkowe dla zmiennych <i>x</i> i <i>y</i> , gdyż protokół aktualizuje dane tylko podczas wykonywania operacji synchronizujących. Proces <i>p2</i> wykonuje operację <i>acquire</i> na zamku, który wcześniej zajmowany był przez proces <i>p1</i> , co powoduje przesłanie aktualizacji z <i>p1</i> do <i>p2</i> . Dzięki temu kolejne odczyty, zarówno zmiennej <i>x</i> jak i <i>y</i> odzwierciedlają modyfikacje dokonane przez proces <i>p1</i> . Jeżeli stosowany jest protokół unieważniania, to odwołanie do strony, gdzie znajduje się zmienna <i>x</i> lub zmienna <i>y</i> spowoduje pobranie aktualnej wersji tej strony z węzła <i>p1</i>.<br>
                    <br>
                    <p>
                    Podsumowując: węzeł, który zwalnia blokadę przekazuje węzłowi, który przejmuje blokadę informacje o <i>wszystkich</i> modyfikacjach, których węzeł docelowy nie zna. Do reprezentacji historii przetwarzania i wydzielania fragmentów historii nieznanych innym węzłom stosuje się wektorowe etykiety czasowe.<br>
                    </p>
                    <p>
                    <br>
                    </p>
                    <p>
                    Operacje synchronizujące mogą być wykonywane współbieżnie na wielu serwerach, ponieważ istnieje wiele zamków.
                    </p>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność zakresu</font></b><br>
                    <hr size=2><a href=http://wazniak.mimuw.edu.pl/index.php?title=Sr-9-wyk-1.0-Slajd36 title=Sr-9-wyk-1.0-Slajd36> </a><br>
                    </div>
                    <div id=mid2 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2539dtjs4dhp_b.png" style=HEIGHT:344px;WIDTH:500px><br>
                    <br>
                    Spójność zakresu (ang. <i>scope</i> <i>consistency</i> ) jest dalszą modyfikacją przetwarzania obserwowanego w spójności zwalniania. Wymiana informacji następuje tu tak samo jak w przypadku protokołu <i>lazy</i> <i>release</i> , a więc przy wywoływaniu operacji <i>acquire</i> . Zmienia się jednak zakres tej informacji. O ile spójność zwalniania wymagała przesłania <i>wszystkich</i> informacji nieznanych węzłowi docelowemu, o tyle w spójności zakresu przesyłane są tylko te modyfikacje, które zostały wykonane od ostatniej operacji <i>acquire</i> na żądanym zamku. Najprawdopodobniej bowiem to właśnie te dane są potrzebne zajmującemu blokadę procesowi, a nie te, które były modyfikowane wcześniej czy później. Oczywistą konsekwencją tego rozwiązania jest zmniejszenie rozmiarów przesyłanych komunikatów. Informacja aktualizacyjna przesyłana jest tylko do węzła, który jej potrzebuje i w takim zakresie, jakiego potrzebuje.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność zakresu - przykład</font></b><br>
                    <hr size=2><br>
                    <div id=wm8q style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2540dmwbwxgz_b.png" style=HEIGHT:344px;WIDTH:500px><br>
                    <br>
                    Rysunek przedstawia przykładowe przetwarzanie tożsame z tym, które było prezentowane w przypadku spójności zwalniania. W systemie stosującym spójność zakresu również nastąpi synchronizacja danych w momencie wykonywania operacji <i>acquire</i> . Jednakże proces <i>p2</i> nie zostanie poinformowany o modyfikacjach zmiennej <i>y</i> , ponieważ była ona modyfikowana przed zakresem wyznaczonym operacją <i>acquire</i> . Poprawny dostęp do zmiennej <i>y</i> wymagałby w tym przypadku: przesunięcia operacji <i>acquire</i> przed zapis do <i>y</i> lub użycie innej zmiennej synchronizującej i wskazanie nowego zakresu, do którego można by się odwołać w procesie <i>p2</i> .<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Spójność wejścia</font></b><br>
                    <hr size=2><br>
                    <div id=jvq8 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2541hnxt3dcg_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    W spójności zwalniania i spójności zakresu zmienne synchronizujące są luźno związane ze zmiennymi współdzielonymi. To programista w swojej głowie ustala, że np. dostęp do zmiennej <i>x</i> chroniony będzie zamkiem <i>L1</i> , a do zmiennej <i>y</i> zamkiem <i>L2</i> . Inaczej jest w przypadku spójności wejścia, gdzie programista ma obowiązek jawnego powiązania każdego obiektu współdzielonego z jakąś zmienną synchronizującą. Dzięki takiemu rozwiązaniu następuje jeszcze bardziej precyzyjny transfer aktualizacji pomiędzy serwerami, ponieważ system wie na podstawie zlecanych operacji synchronizujących które obiekty ma aktualizować. Niestety wadą tego modelu jest konieczność definiowania wielu zmiennych synchronizacyjnych i konieczność ustalania powiązań między nimi.
                    <p>
                    <br>
                    </p>
                    <p>
                    Dodatkową cechą spójności wejścia jest wyróżnienie dwóch typów operacji <i>acquire</i>&nbsp;: zajęcie zamka może być w trybie wyłącznym lub dzielonym. Umożliwia to realizację współbieżnego odczytu tych samych danych na wielu węzłach, co nie było możliwe w przypadku spójności zwalniania i zakresu.
                    </p>
                    <br>
                    <br>
                    </div>
                    <b style=COLOR:#3d85c6><font size=3>Własność lokalności</font></b><br>
                    <hr size=2>
                    </div>
                    <br>
                    </div>
                    <div id=nn0p style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2542pmgxddw_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    W analizie modeli spójności używa się niekiedy pojęcia <b>lokalności</b> (ang. <i>locality</i> ), której definicja zawarta jest na slajdzie. Lokalność jest cechą modeli spójności atomowej i podręcznej. W przypadku spójności podręcznej jest to dość naturalne, bo definicja modelu odnosi się właśnie do pojedynczych obiektów. Jeżeli więc zapisy do każdego pojedynczego obiektu są globalnie uporządkowane, to cały system zachowuje spójność podręczną.<br>
                    <br>
                    <br>
                    <b style=COLOR:#3d85c6><font size=3>Własność lokalności - przykład</font></b><br>
                    <hr size=2><br>
                    <div id=d414 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2543cvk2dmgn_b.png" style=HEIGHT:341px;WIDTH:500px><br>
                    <br>
                    Przykład na slajdzie (prezentowany dalej na kolejnych dwóch slajdach) ma na celu zaprezentowanie, że spójność sekwencyjna nie ma własności lokalności. W przykładzie proces <i>p1</i> dokonuje zapisów do 4 zmiennych: <i>x1</i> , <i>x2</i> , <i>y1</i> i <i>y2</i> . Proces <i>p2</i> jedynie czyta te zmienne. Jak łatwo zauważyć obraz historii przetwarzania w procesie <i>p2</i> zawiera inną kolejność operacji zapisu do zmiennych <i>x2</i> i <i>y1</i> niż obraz w procesie <i>p1</i> . Nie jest zachowana więc spójność sekwencyjna. Pomimo, że... (nast. slajd)<br>
                    <br>
                    <br>
                    <div id=qr9i style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2544zpshsvf5_b.png" style=HEIGHT:342px;WIDTH:500px><br>
                    <br>
                    Rysunek przedstawia fragment przetwarzania z poprzedniego slajdu dotyczący operacji na zmiennych <i>x1</i> i <i>x2</i> . Jak widać z obrazów historii przetwarzania operacje na takim podzbiorze zmiennych są spójne sekwencyjnie. Ale... (nast. slajd)<br>
                    <br>
                    <br>
                    <div id=d6h4 style=TEXT-ALIGN:left>
                    <img src="images/dcjpvv6n_2545gfr7mxhc_b.png" style=HEIGHT:343px;WIDTH:500px><br>
                    <br>
                    Rysunek przedstawia inny fragment przetwarzania z wcześniejszego slajdu dotyczący operacji na zmiennych <i>y1</i> i <i>y2</i> . Jak widać z obrazów historii przetwarzania operacje na takim podzbiorze zmiennych również są spójne sekwencyjnie. Niestety na podstawie analizy dla tych dwóch podzbiorów zmiennych nie możemy powiedzieć, że system jako całość zachowuje spójność sekwencyjną. Oznacza to, że spójność sekwencyjna nie ma własności lokalności.<br>
                    <br>
                    <p>
                    Wracając do pełnego przykładu – spójność atomowa posiada własność lokalności, ponieważ uwzględniane są uporządkowania operacji w czasie rzeczywistym. W takim przypadku kolejność operacji <i>w(x2)1</i> i <i>w(y1)1</i> z procesu <i>p1</i> musiałaby być zachowana w obrazie historii w procesie <i>p2</i> .
                    </p>
                    <br>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                    </div>
                  </div>
                </div>
              </div>
            </div>
          </div>
        </div>
      </div>
    </div>
  </div>
</div>
<br></body>
</html>